The present invention relates to the field of cell-based parallel processing systems composed of a regular collection of processing cells whose behavior is controlled by software contained within each cell. In particular, it relates to a processing system called the Cell Matrix (U.S. Pat. No. 5,886,537 (Macias, et al.)) composed of self-dual processing cells which each operate in one of two modes, one mode being a data processing mode, and the other being a code processing mode. More particularly, it relates to configurations of such cells to enable non-adjacent cells to interact with each other as if they were adjacent.
Self-dual processing cells are programmable logic devices which can interchangeably process both data and code. Such cells are self-dual in that they are able to both configure other cells and be configured by other cells. Collections of self-dual cells can be assembled into a self-reconfigurable system, called a cell matrix. U.S. Pat. No. 5,886,537 discusses in detail such self-dual processors as well as their assembly into a processing matrix.
Devices such as field programmable gate arrays (FPGAs) and programmable logic devices (PLDs) generally employ mechanisms to allow their programmable blocks to interact with each other despite their possibly non-adjacent locations. For example, U.S. Pat. No. 5,212,652 (Agrawal, et al.) describes an interconnect system to allow flexible connection among the device's logic blocks, including connections between blocks on opposite sides of the device.
In contrast, the cells within a cell matrix interact only with nearby cells which are adjacent according to a fixed, pre-defined system topology. This simple interaction scheme has several advantages over more sophisticated routing systems.
Since both data and configuration information are exchanged only among small sets of neighbors, there is no need for system-wide address and data buses. Since the set of possible sources and destinations is limited to the number of adjacent cells, the size of each cell's address space is fixed, independent of the total number of cells in the system.
Hence a matrix of such cells is infinitely scalable, in that two such matrices can simply be attached along their boundaries, with adjacent boundary cells connected between the two matrices, to produce a larger matrix. This scalability has profound advantages in terms of manufacturing large cell matrices. This simple interconnection scheme also has tremendous benefits in terms of fault tolerance, since it eliminates most architecturally-critical failure points.
Additionally, the presence of local control at all points within the matrix allows reconfiguration tasks to be distributed throughout the matrix, allowing multiple configurations to be performed in parallel. This offers dramatic speedup potential of configuration tasks for extremely large matrices as compared to an externally-configured device.
It is therefore clear that the local-only interaction scheme of a cell matrix has definite advantages over a system with centralized control and global communications, such as an FPGA. However, these advantages come at a price. Because cells are only configurable by adjacent neighboring cells, there remains the question of how one set of cells can configure another set of non-adjacent remote cells. Since any cell has direct access to only a small, fixed number of adjacent neighboring cells, there is no direct way to configure collections of cells, i.e., there is no direct way to build useful circuits.
This is also a problem in trying to bootstrap an empty cell matrix. In a two-dimensional matrix, only cells which lie along an edge are directly accessible from outside the matrix. There is no way to access internal cells except via their neighbors, which may themselves be internal (non-edge) cells, and therefore only be accessible by their neighbors, and so on. There is thus no direct way for an external controller to configure internal cells within a cell matrix.